package _05_二叉树;

public class _572_另一棵树的子树 {

    private static final String EMPTY = "#";

    private static final String SPLIT = "!";

    // 求一个树的子树，要么是当前节点的树，要么就是左子树，要么就是右子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        return isSame(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null || root.val != subRoot.val) return false;
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }

    // 对于前序遍历，需要注意，开始序列化，也要进行分割操作
    // 序列化树，判断是字符串的包含情况
    public boolean isSubtree1(TreeNode root, TreeNode subRoot) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        postSerialize(root, sb1);
        postSerialize(subRoot, sb2);
        return sb1.toString().contains(sb2);
    }

    // 后续遍历，序列化字符串
    private void postSerialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(EMPTY).append(SPLIT);
            return;
        }
        postSerialize(node.left, sb);
        postSerialize(node.right, sb);
        // 拼接字符串
        sb.append(node.val).append(SPLIT);
    }
}
